package com.kaizen.leet28;

/**
 * 28.给定一个 haystack 字符串和一个 needle 字符串，
 * 在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
 *
 * 阮一峰 KMP
 * http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
 *
 * @author kaizen
 * @date 2020/4/19 15:50
 */
class SolutionKaizen {


    /**
     * 每个字串都进行匹配
     * @param haystack
     * @param needle
     * @return
     */
    public  int strStr(String haystack, String needle) {
        if (needle == null || "".equals(needle.trim())) {
            return 0;
        }
        char[] stacks = haystack.toCharArray();
        char[] needles = needle.toCharArray();
        int cs = stacks.length;
        int ns = needles.length;
        if (ns > cs) {
            return -1;
        }
        int i = 0;
        for (; i < cs; i++) {
            int j = 0;
            int k = i;
            while (j < ns && k < cs) {
                if (needles[j] != stacks[k]) {
                    break;
                }
                if (j == ns -1) {
                    return i;
                }
                k++;
                j++;
            }
            // 这里的长度不够匹配ns的长度或者已经到最后一次 直接返回-1
            if ((cs-i+1) < ns || i == cs - 1) {
                return -1;
            }
        }
        return i;

    }
}
